/*
  Grupo 2
  
  Luiz Felipe de Souza Mattos 	RA 107822
  
  Debora Maia Silva 	      	RA 101985

*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "heap.h"

/* cria um heap vazio */
Heap* criaListaHeap(void)
{
	return NULL;
}

/* "sobe" um valor de frequencia no heap para coloca-lo na posicao correta */
void sobe(Heap *p,int posicao)
{
	int i;
	Info aux;

	i = (posicao - 1)/2;

	aux = p->vet[posicao];

	while (posicao > 0 && p->vet[i].freq > aux.freq)
	{
		p->vet[posicao] = p->vet[i];
		posicao = i;
		i = (i - 1)/2;
	}
	p->vet[posicao] = aux;
}

/* insere um novo elemento no heap */
void insere(Heap *p, Info info)
{
	p->vet[p->tam] = info;
	p->tam += 1;
	sobe(p,p->tam - 1);
}

/* "desce" um valor de frequencia no heap para coloca-lo na posicao correta */
void desce(int posicao, int tam, Info *vet)
{ 
   int i = 2*posicao;
	Info aux;

	aux = vet[posicao];

   	while (i <= tam)
	{
      	if (i < tam && vet[i].freq < vet[i + 1].freq)
			++i;
      	if (aux.freq >= vet[i].freq)
			break;
      	vet[posicao] = vet[i];
      	posicao = i;
		i = 2*posicao;
   	}
   	vet[posicao] = aux;
}

/* algoritmo de ordenacao por ordem crescente do heap */
void heapsort (int tam, Info *vet)
{
   	int i, j;
	Info aux;

  	for (i = tam/2; i >= 1; --i)
    		desce(i, tam, vet);
   	for (j = tam;j >= 2;--j) 
	{
		aux = vet[1];
		vet[1] = vet[j];
		vet[j] = aux;
		desce(1,j-1,vet);
   	}
}

/* remove o elemento de maior prioridade e coloca as informacoes em uma variavel 
passada por referencia */
void removeHeap(Heap *p,Info *info)
{
	Info aux;
	int i;

	*info = p->vet[0];
	p->tam -= 1;
	p->vet[0] = p->vet[p->tam];
	for (i = 1;i < p->tam + 1;i++)
	{
		aux = p->vet[i];
		p->vet[i - 1] = aux;
	}
	p->vet[p->tam].carac = 0;
	p->vet[p->tam].freq = 0;
}

/* ordena no heap as letras de mesma frequencia por ordem crescente da tabela asc */
void organiza(Heap *info,int indice)
{
	Info aux;
	
	if (indice == 256 || info->vet[indice].freq == 0)
		return;

	if (info->vet[indice].freq == info->vet[indice + 1].freq && 
	info->vet[indice].carac > info->vet[indice + 1].carac)
	{
		aux = info->vet[indice];
		info->vet[indice] = info->vet[indice + 1];
		info->vet[indice + 1] = aux;
		organiza(info,indice - 1);	
	}
	organiza(info,indice + 1);
}

/* insere 0 em todas as casas de um vetor de inteiros */
void zera(int *carac)
{
	int i;

	for (i = 0;i < 256;i++)
		carac[i] = 0;
}

/* inicializa as informacoes do heap */
void zeraHeap(Info *info)
{
	int i;

	for (i = 0;i < 256;i++)
	{
		info[i].carac = 0;
		info[i].freq = 0;
	}
}

/* insere todas as letras e respectivas frequencias na lista heap */
Heap * MontaHeap(int *vet)
{
	int i;
	Heap *p;
	Info aux;

	p = malloc(sizeof(Heap));
	zeraHeap(p->vet);
	p->tam = 0;

	for (i = 0;i < 256;i++)
	{
		if (vet[i] != 0)
		{
			aux.freq = vet[i];
			aux.carac = (unsigned char)i;
			insere(p,aux);
		}
	}

	return p;
}

/* le o arquivo, e vai contando a frequencia de carda caractere e depois 
ordena de acordo com a frequencia e para frequencias iguais, de acordo 
com o indice na tabela ASCII */
Heap * ContaeOrdena(FILE *arquivo)
{
	int carac[256];
	Heap *lista;
	unsigned char a;

	zera(carac);

	while (!feof(arquivo))
	{
		fscanf(arquivo,"%c",&a);

		if (!feof(arquivo))
		{
			if ((int)a >= 0)
				carac[(int)a] += 1;
			else
				carac[256 + (int)a] += 1;
		}
	}
	/* monta o heap */
	lista = MontaHeap(carac);
	/* ordena o heap */
	heapsort(lista->tam - 1,lista->vet);
	/* organiza as letras de mesma frequencia por ordem crescente da tabela asc */
	organiza(lista,0);

	return lista;

}

/* libera a memoria usada pelo heap */
void LiberaHeap(Heap **p)
{
	free(*p);
	*p = NULL;
	p = NULL;
}

